
/**
 * 动态规划实现找零
 * @param {Array} coins 硬币数组
 * @param {Number} total 零钱总数
 */
function minCoins(coins, total) {

    let T = [];//T是一个二维数组,用来存表格
    let n = coins.length;

    for (let i = 0; i < n; i++) {//外循环控制硬币数组

        T[i] = [];

        //核心:硬币找零
        for (let j = 0; j <= total; j++) {

            if (j == 0) {
                T[i][j] = 0;//第1列全为0
                continue;
            }
            if (i == 0) {
                T[i][j] = j / coins[i];//第1行全部为无穷大
            }
            else {
                //如果当前存在值,用当前值去比较
                if (j > coins[i]) {
                    //如果硬币面值比零钱数小
                    //第i行 当前列往前数coins[i](硬币面值)的列 的值+1和
                    // 当前值的上一行同一列的值比较,即T[i-1][j] 
                    //取最小值
                    T[i][j] = (T[i][j - coins[i]] + 1 <= T[i - 1][j]) ? T[i][j - coins[i]] + 1 : T[i - 1][j];
                } else {
                    //硬币面值比零钱大,直接赋值上一列
                    T[i][j] = T[i - 1][j];
                }

            }
        }
    }

    //查找最优解
    findValue(coins,total,n,T);
    return T;

}

/**
 * 查询最优解 
 * 倒叙查询 选择当前硬币值j 向上查询T[i][total - j] 和 coins[i]
 * @param {Array} coins 
 * @param {Number} total 
 * @param {Number} n 
 * @param {Array} T 
 */
function findValue(coins,total,n,T){

    var i = n-1, j = total;
    let s = [];//储存组合结果
    while(i >= 0 && j > 0 ){
		
		s.push(coins[i]);
		j=j-coins[i];//向上查找列
		if(j <= 0){
			break; //计算结束，退出循环
		}
		//如果 i == 0,那么就在第 0 行一直循环计算，直到 j=0即可
		if(i>0){
            //console.log(i);
            //和上一行比较,T[i][j] - T[i-1][j] 零钱余额为0
			while(T[i][j] == T[i-1][j]){
				i--;
				if(i== 0){
					break;
				}
			}
		}
	}
	console.log(s);

}

// let coins = [1,2,5,6];
// let total = 11
let coins = [5,4,2,3,7];
let total = 6
console.log(minCoins(coins,total));
